package com.qch.leecode.cyc2018.algorithm.a1_double_pointer;

import java.util.Arrays;
import java.util.List;

/**
 * 算法思想：双指针：524. 通过删除字母匹配到字典里最长单词
 * https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/
 * <p>
 *
 * 解题思路：
 * 1.了解字母序
 *
 * 自己问题：
 * 看不懂题目，为空判断不准确
 *
 * @Author qch
 * @Date 2022/11/10
 * <p>
 *
 * 题目：
 * 给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
 * 如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。
 *
 * <p>
 * 输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
 * 输出："apple"
 *
 * 输入：s = "abpcplea", dictionary = ["a","b","c"]
 * 输出："a"
 */
public class L7_LongestWord524 {
    public static void main(String[] args) {
        String s="abpcplea";
        List arr=Arrays.asList("ale","apple","monkey","plea");
        String longestWord = own_better_findLongestWord(s, arr);
        System.out.println(longestWord);
      //String compare = compare("abc", "b");
//       int m = "ab".compareTo("abc");
//        System.out.println(m);
    }
    public static String own_better_findLongestWord(String s, List<String> dictionary) {
        String longest="";
        for (String dic : dictionary) {
            //s的指针
            int o=0;
            //str的指针
            int d=0;
            //s.length()>dic.length()小于的话是肯定不存在的
            while (dic.length()>=longest.length()&&d<dic.length()&&o<s.length()&&s.length()>=dic.length()){
                if(dic.charAt(d)==s.charAt(o))
                {
                    //对比到最后一个字符串
                    if(d==dic.length()-1)
                    {
                        longest=compareBetter(longest,dic);
                        break;
                    }
                    d++;
                }
                o++;
            }
        }
        return longest;
    }

    public static String compareBetter(String a,String b) {
        if (a.length() == b.length()) {
            int i = 0;
            while (i < a.length()) {
                if (a.charAt(i) == b.charAt(i)) {
                    i++;
                } else if (a.charAt(i) > b.charAt(i)) {
                    return b;
                } else {
                    return a;
                }
            }
        }
        return b;
    }
    public static String own_findLongestWord(String s, List<String> dictionary) {
        String longest="";
        for (String dic : dictionary) {
            //s的指针
            int o=0;
            //str的指针
            int d=0;
            //s.length()>dic.length()小于的话是肯定不存在的
            while (d<dic.length()&&o<s.length()&&s.length()>=dic.length()){
                if(dic.charAt(d)==s.charAt(o))
                {
                    //对比到最后一个字符串
                    if(d==dic.length()-1)
                    {
                        longest=compare(longest,dic);
                        break;
                    }
                    d++;
                    o++;
                }else {
                    o++;
                }
            }
        }
        return longest;
    }
    //这个可以直接用compareTo（）方法
    public static String compare(String a,String b)
    {
        if (a.length() > b.length()) {
            return a;
        } else if (a.length() < b.length()) {
            return b;
        } else {
            int i=0;
            while (i < a.length()) {
                if (a.charAt(i) == b.charAt(i)) {
                    i++;
                }else if (a.charAt(i) > b.charAt(i)) {
                    return b;
                }else {
                    return a;
                }
            }
            return a;
        }
    }


}
